package 中等.贪心思想;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
 * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，
 * 如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
 * 0 <= j <= nums[i] 
 * i + j < n
 * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/jump-game-ii
 */
public class 跳跃游戏II_45 {

    public static void main(String[] args) {

    }

    /**
     * 广度优先搜索
     */
    public int jump(int[] nums) {
        if (nums.length == 1) return 0;
        int count = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(0);

        boolean[] visited = new boolean[nums.length];

        while (!queue.isEmpty()) {
            int size = queue.size();
            count++;
            while (size-- > 0) {
                Integer cur = queue.pollFirst();

                if (cur + nums[cur] >= nums.length - 1) {
                    return count;
                }
                for (int i = 1; i <= nums[cur]; i++) {
                    if (!visited[cur + i]) {
                        queue.addLast(cur + i);
                        visited[cur + i] = true;
                    }
                }
            }
        }

        return count;
    }

    /**
     * 贪心思想
     * 假如当前位置为 i ，下一个可以到达的位置是
     * i+0 , i+1 , i+2 , i+nums[i]，那么我应该跳
     * 到哪个位置呢，可以计算这些位置可以到达的最远位置
     * 贪心的跳到那个位置
     */
    public int jump2(int[] nums) {
        if (nums.length == 1) return 0;
        int count = 0;

        int idx = 0;
        while (idx < nums.length) {
            count++;
            if (idx + nums[idx] >= nums.length - 1) {
                return count;
            }

            int nextIdx = idx + 1;
            for (int i = 1; i <= nums[idx]; i++) {
                if (idx + i + nums[idx + i] > nextIdx + nums[nextIdx]) {
                    nextIdx = idx + i;
                }
            }
            idx = nextIdx;
        }
        return count;
    }

}
